|
The Zarankiewicz problem, an unsolved problem in mathematics, asks for the largest possible number of edges in a bipartite graph that has a given number of vertices but has no complete bipartite subgraphs of a given size.〔. Reprint of 1978 Academic Press edition, .〕 It belongs to the field of extremal graph theory, a branch of combinatorics, and is named after the Polish mathematician Kazimierz Zarankiewicz, who proposed several special cases of the problem in 1951.〔. As cited by .〕 The Kővári–Sós–Turán theorem, named after Tamás Kővári, Vera T. Sós, and Pál Turán, provides an upper bound on the solution to the Zarankiewicz problem. When the forbidden complete bipartite subgraph has one side with at most three vertices, this bound has been proven to be within a constant factor of the correct answer. For larger forbidden subgraphs, it remains the best known bound, and has been conjectured to be tight. Applications of the Kővári–Sós–Turán theorem include bounding the number of incidences between different types of geometric object in discrete geometry. ==Problem statement== A bipartite graph ''G'' = (''U'', ''V'', ''E'') consists of two disjoint sets of vertices ''U'' and ''V'', and a set of edges each of which connects a vertex in ''U'' to a vertex in ''V''. No two edges can both connect the same pair of vertices. A complete bipartite graph is a bipartite graph in which every pair of a vertex from ''U'' and a vertex from ''V'' is connected to each other. A complete bipartite graph in which ''U'' has ''s'' vertices and ''V'' has ''t'' vertices is denoted ''K''''s'',''t''. If ''G'' = (''U'', ''V'', ''E'') is a bipartite graph, and there exists a set of ''s'' vertices of ''U'' and ''t'' vertices of ''V'' that are all connected to each other, then these vertices induce a subgraph of the form ''K''''s'',''t''. (In this formulation, the ordering of ''s'' and ''t'' is significant: the set of ''s'' vertices must be from ''U'' and the set of ''t'' vertices must be from ''V'', not vice versa.) The Zarankiewicz function ''z''(''m'', ''n''; ''s'', ''t'') denotes the maximum possible number of edges in a bipartite graph ''G'' = (''U'', ''V'', ''E'') for which |''U''| = ''m'' and |''V''| = ''n'', but which does not contain a subgraph of the form ''K''''s'',''t''. As a shorthand for an important special case, ''z''(''n''; ''t'') is the same as ''z''(''n'', ''n''; ''t'', ''t''). The Zarankiewicz problem asks for a formula for the Zarankiewicz function, or (failing that) for tight asymptotic bounds on the growth rate of ''z''(''n''; ''t'') assuming that ''t'' is a fixed constant, in the limit as ''n'' goes to infinity. For ''s = t = 2'' this problem is the same as determining cages with girth six. The Zarankiewicz problem, cages and finite geometry are strongly interrelated.〔http://www.cs.elte.hu/~hetamas/publ/DHSzFIN.pdf〕 The same problem can also be formulated in terms of digital geometry. The possible edges of a bipartite graph ''G'' = (''U'', ''V'', ''E'') can be visualized as the points of a |''U''| × |''V''| rectangle in the integer lattice, and a complete subgraph is a set of rows and columns in this rectangle in which all points are present. Thus, ''z''(''m'', ''n''; ''s'', ''t'') denotes the maximum number of points that can be placed within an ''m'' × ''n'' grid in such a way that no subset of rows and columns forms a complete ''s'' × ''t'' grid.〔 An alternative and equivalent definition is that ''z''(''m'', ''n''; ''s'', ''t'') is the smallest integer ''k'' such that every (0,1)-matrix of size ''m'' × ''n'' with ''k'' + 1 ones must have a set of ''s'' rows and ''t'' columns such that the corresponding ''s''×''t'' submatrix is made up only of 1's. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Zarankiewicz problem」の詳細全文を読む スポンサード リンク
|